
/**
 * 
 * 字符串化繁为简
 * 
 * 题目描述

给定一个输入字符串，字符串只可能由英文字母（ 'a' ~ 'z'、'A' ~ 'Z' ）和左右小括号（ '('、')' ）组成。

当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含1个或多个英文字母，也可以不包含英文字母。

当小括号对内包含多个英文字母时，这些字母之间是相互等效的关系，而且等效关系可以在不同的小括号对之间传递，即当存在 'a' 和 'b' 等效和存在 'b' 和 'c' 等效时，'a' 和 'c' 也等效，另外，同一个英文字母的大写字母和小写字母也相互等效（即使它们分布在不同的括号对里）

需要对这个输入字符串做简化，输出一个新的字符串，输出字符串里只需保留输入字符串里的没有被小括号对包含的字符（按照输入字符串里的字符顺序），并将每个字符替换为在小括号对里包含的且字典序最小的等效字符。

如果简化后的字符串为空，请输出为"0"。

示例 :
输入字符串为"never(dont)give(run)up(f)()"，初始等效字符集合为('d', 'o', 'n', 't')、('r', 'u', 'n')，由于等效关系可以传递，因此最终等效字符集合为('d', 'o', 'n', 't', 'r', 'u')，将输入字符串里的剩余部分按字典序最小的等效字符替换后得到"devedgivedp'

输入描述
input_string

输入为1行，代表输入字符串

输出描述
output_string

输出为1行，代表输出字符串

备注
输入字符串的长度在1~100000之间

用例
输入	()abd
输出	abd
说明	输入字符串里没有被小括号包含的子字符串为"abd"，其中每个字符没有等效字符，输出为"abd"
输入	(abd)demand(fb)()for
输出	aemanaaor
说明	等效字符集为('a', 'b', 'd', 'f')，输入字符串里没有被小括号包含的子字符串集合为'demandfor"，将其中字符替换为字典序最小的等效字符后输出为："aemanaaor"
输入	()happy(xyz)new(wxy)year(t)
输出	happwnewwear
说明	等效字符集为(‘x’, 'y', 'z', 'w')，输入字符串里没有被小括号包含的子字符串集合为"happynewyear"，将其中字符替换为字典序最小的等效字符后输出为："happwnewwear"
输入	()abcdefgAC(a)(Ab)(C)
输出	AAcdefgAC
说明	等效字符集为('a', 'A', 'b')，输入字符里没有被小括号包含的子字符串集合为"abcdefgAC"，将其中字符替换为字典序最小的等效字符后输出为："AAcdefgAC"

 * 
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

/**
  * 题目解析
本题首先需要将：

输入字符串里的没有被小括号对包含的字符（主体字符）
输入字符串里的被小括号对包含的字符（等效字符）
这两部分内容解析出来。

我的思路是，定义一个标志 isOpen = fasle，表示有没有遇到 '(' 字符，初始时肯定没遇到，因此初始化为false。

然后开始遍历输入字符串的每一个字符c：

如果 c == '('，则将isOpen=true，并新建一个等效字符容器eq
如果 c == ')'，则将isOpen=false
如果 c 是其他字符，如果此时isOpen==true，则将c加入“等效字符容器eq”中，否则将c加入“主体字符cArr”容器中。
这样，我们就可以得到了一个（主体字符容器）和多个（等效字符容器）。

接下来，就是对等效字符容器，进行合并操作，两个等效字符容器可以合并的原则是：

存在相同的字符
虽然不存在相同字符，但是一个有大写字符，另一个由小写字符
这个合并操作，目前没有想到好办法，只能暴力合并。具体请看代码实现。

最后，遍历每一个合并后的等效字符容器，求出对应容器中字典序最小的字符，作为容器内其他字符的替换字符。按照此替换规则，来替换主体字符容器中对应的字符。

  */
public class 字符串化繁为简 {
    
    public static void main(String[] args) {
    

        try{

            Scanner scanner = new Scanner(System.in);

            String inputStr = scanner.nextLine();

            // 主体字符容器
            StringBuilder builder = new StringBuilder();
    
            // 等效字符容器
            ArrayList<Character> list = new ArrayList<>();
    
            UnionFindSet ufs = new UnionFindSet(128);
            HashSet<Character> set = new HashSet<>();

            boolean isopen = false;

            //解析除 () 内 外的值
            for(char c : inputStr.toCharArray()){

                if(c == '('){
                    isopen = true;
                } else if(c == ')'){
                    isopen = false;

                    if (list.isEmpty()) continue;
 
                char base = list.get(0);
 
                // 等效传递（利用并查集）
                for (Character letter : list) {
                    // 不同括号间的大小写字母可以形成等效传递, 比如括号1中 (abc), 括号2中 (AXY), 则两个括号的a,A形成等效传递，最终:a,b,c,A,X,Y互相等效
                    char upper = Character.toUpperCase(letter);
                    char lower = Character.toLowerCase(letter);
 
                    // set记录的是之前括号里面出现过的字母
                    if (set.contains(lower)) {
                        ufs.union(letter, lower); // 括号间等效传递（利用并查集）
                    }
 
                    if (set.contains(upper)) {
                        ufs.union(letter, upper); // 括号间等效传递（利用并查集）
                    }
 
                        ufs.union(letter, base); // 括号内等效传递
                    }
    
                    // 将当前()内字符加入set
                    set.addAll(list);
                    // 清空list, 用于收集下个()内的字母
                    list.clear();

                } else if(isopen){

                    //在括号内
                    list.add(c);
                } else{

                    //在括号外
                    builder.append(c+"");
                }
        


            }

            // 等效替换
            char[] cArr = builder.toString().toCharArray();
            for (int i = 0; i < 128; i++) {
                char ch = ((char) i);
                char fa = ((char) ufs.find(i)); // 找到ch字母的等效的字典序最小的字母fa
    
                // 将ch替换为fa
                for (int j = 0; j < cArr.length; j++) {
                    if (cArr[j] == ch) {
                        cArr[j] = fa;
                    }
                }
            }
    
            String res = new String(cArr);
            System.out.println(res.isEmpty() ? "0" : res); // 如果简化后的字符串为空，请输出为"0"


        }catch(Exception e){
            e.printStackTrace();
        }

    }

    //并查集
    public static class UnionFindSet {
    
        int[] fa;

        public UnionFindSet(int n) {
            this.fa = new int[n];
            for (int i = 0; i < n; i++) fa[i] = i;
        }
     
        public int find(int x) {
            if (x != this.fa[x]) {
                this.fa[x] = this.find(this.fa[x]);
                return this.fa[x];
            }
            return x;
        }
     
        public void union(int x, int y) {
            int x_fa = this.find(x);
            int y_fa = this.find(y);
     
            // 保证字典序小的字符优先为根
            if (x_fa < y_fa) {
                this.fa[y_fa] = x_fa;
            } else {
                this.fa[x_fa] = y_fa;
            }
        }
        
    }
}
